import java.util.*;


//数据流中的第K大元素
class KthLargest{
    PriorityQueue<Integer> heap;
    int _k;

    public KthLargest(int k , int[] nums){
        _k = k;
        heap = new PriorityQueue<>();
        for (int x: nums) {
            heap.offer(x);
            if (heap.size()>_k){
                heap.poll();
            }
        }
    }

    public int add(int val){
        heap.offer(val);
        if (heap.size() >_k){
            heap.poll();
        }
        return heap.peek();
    }
}




//数据流的中位数
class MedianFinder{
    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    public MedianFinder(){
        left = new PriorityQueue<>((a,b)->b-a);//大根堆
        right = new PriorityQueue<>((a,b)->b-a);//小根堆
    }

    public void addNum(int num){
        //分情况讨论
        if (left.size() == right.size()){
            if (left.isEmpty() || num<=left.peek()){
                left.offer(num);
            }else{
                right.offer(num);
                left.offer(right.poll());
            }
        }else{
            if (num<=left.peek()){
                left.offer(num);
                right.offer(left.poll());
            }else{
                right.offer(num);
            }
        }
    }

    public double findMedian(){
        if (left.size() == right.size()) return (left.peek() +right.peek())/2.0;
        else return left.peek();
    }
}





public class Test {




    //前K个高频单词
    public List<String> topKFrequent(String[] words,int k){
        //统计每个单词出现的次数
        Map<String,Integer> hash = new HashMap<>();
        for (String s: words) {
            hash.put(s,hash.getOrDefault(s,0)+1);
        }

        //创建一个大小位K的堆
        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
                (a,b)->{
                    if (a.getValue().equals(b.getValue())){
                        //次数相同，则按字典顺序大根堆方式排列
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue()-b.getValue();
                }
        );

        //TopK的组逻辑
        for(Map.Entry<String,Integer> e : hash.entrySet()){
            heap.offer(new Pair<>(e.getKey(),e.getValue()));
            if (heap.size() > k){
                heap.poll();
            }
        }

        //提取结果
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()){
            ret.add(heap.poll().getKey());
        }
        //逆序数组
        Collections.reverse(ret);
        return ret;
    }







    //最后一块石头的重量
    public int lastStoneWeight(int[] stones){
        //创建大根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b)->b-a);

        for (int x: stones) {
            heap.offer(x);
        }

        while(heap.size() >1){
            int a = heap.poll();
            int b = heap.poll();
            if (a>b){
                heap.offer(a-b);
            }
        }
        return heap.isEmpty() ? 0 :heap.peek();
    }


}
